/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<TreeNode, TreeNode> parentMap = new HashMap<>();
    Set<TreeNode> pParents = new HashSet<>();
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 找到所有节点的父节点
        fillParentMap(root);
        // 找到P节点的所有父节点（老师讲的标红过程）
        for (TreeNode node = p; node != null; node = parentMap.get(node)) {
            pParents.add(node);
        }
        // 找到q节点的父节点，看是否在p父节点中，返回第一个    
        for (TreeNode node = q; node != null; node = parentMap.get(node)) {
            if (pParents.contains(node)) {
                return node;
            }
        }
        return root;
    }
    private void fillParentMap(TreeNode node) {
        if (node.left != null) {
            parentMap.put(node.left, node);
            fillParentMap(node.left);
        }
        if (node.right != null) {
            parentMap.put(node.right, node);
            fillParentMap(node.right);
        }
    }

}
